/*//#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    while (N--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            int k = 0;
            if (b < 130)
                cout << "duo chi yu!" << ' ';
            else if (b > 130)
                cout << "ni li hai!" << ' ';
            else
                k++;
            if (c < 27)
                cout << "duo chi rou!" << ' ';
            else if (c > 27)
                cout << "shao chi rou!" << ' ';
            else
                k++;
            if (k == 2)
                cout << "wan mei!" << ' ';
        }
        else
        {
            int k = 0;
            if (b < 129)
                cout << "duo chi yu!" << ' ';
            else if (b > 129)
                cout << "ni li hai!" << ' ';
            else
                k++;
            if (c < 25)
                cout << "duo chi rou!" << ' ';
            else if (c > 25)
                cout << "shao chi rou!" << ' ';
            else
                k++;
            if (k == 2)
                cout << "wan mei!" << ' ';
        }
    }
}*/
//#include<bits/stdc++.h>
//using namespace std;
//int a[] = { 2,3,4,5,6,7,8,9 };
//int main()
//{
//    int M;
//    cin >> M;
//    while (M--)
//    {
//        int n;
//        cin >> n;
//        int sum = 0;
//        int k = n;
//        k *= 2;
//        while (k)
//        {
//            sum += k % 10;
//            k /= 10;
//        }
//        int sum1 = 0;
//        int flag = 1;
//        for (int i = 1; i < 8; i++)
//        {
//            sum1 = 0;
//            k = n;
//            k *= a[i];
//            while (k)
//            {
//                sum1 += k % 10;
//                k /= 10;
//            }
//            if (sum != sum1)
//            {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag)
//            cout << sum << endl;
//        else
//            cout << "NO" << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int a[110][110];
//int main()
//{
//    int n, k, x;
//    cin >> n >> k >> x;
//    for (int j = 0; j < n; j++)
//        for (int i = 0; i < n; i++)
//            cin >> a[j][i];
//    int p = 0;
//    for (int i = 1; i < n; i += 2)
//    {
//        p++;
//        if (p > k)
//            p = 1;
//        for (int j = n-1; j >= p; j--)
//            a[j][i] = a[j-p][i];
//        for (int j = 0; j < p; j++)
//            a[j][i] = x;
//    }
//    for (int j = 0; j < n; j++)
//    {
//        long long sum = 0;
//        for (int i = 0; i < n; i++)
//            sum += a[j][i];
//        cout << sum << ' ';
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int a[1000];
//bool is[1000];
//bool IS(int x)
//{
//    for (int i = 2; i <= x / i; i++)
//        if (x % i == 0)
//            return 0;
//    return 1;
//}
//int main()
//{
//    int l, r;
//    cin >> l >> r;
//    int i = max(2, l);
//    int idx = 0;
//    for (; i <= r; i++)
//    {
//        if (is[i] == 0)
//        {
//            is[i] = 1;
//            a[idx++] = i;
//        }
//        for (int j = 0; a[j] * i <= r; j++)
//        {
//            is[a[j] * i] = 1;
//            if (i % a[j] == 0)
//                break;
//        }
//    }
//
//    for (int i = 0; i < idx; i++)
//        for (int j = i + 1; j < idx; j++)
//            for (int k = j + 1; k < idx; k++)
//            {
//                if (IS(a[i] * a[j] + a[k]) && IS(a[i] * a[k] + a[j]) && IS(a[j] * a[k] + a[i]))
//                    cout <<a[i]  << ' ' << a[j] << ' ' << a[k] << endl;
//            }
//    return 0;
//}
//#include<bits/stdc++.h>
//int a[100010], b[100010];
//using namespace std;
//int main()
//{
//    int N, S;
//    cin >> N >> S;
//    unordered_map<int, int>mp;
//    for (int i = 0; i < N; i++)
//        cin >> a[i];
//    for (int i = 0; i < N; i++)
//        cin >> b[i];
//    int k = -S;
//    for (int i = 0; i < N; i++)
//    {
//        if (i % S == 0)
//            k += 2*S;
//        mp[a[i]] = b[- i - 1 + k];
//    }
//    int q;
//    cin >> q;
//    while (q--)
//    {
//        int x;
//        cin >> x;
//        int key = mp[x];
//        if (key)
//            cout << key << endl;
//        else
//            cout << "Wrong Number" << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct A
//{
//    string name;
//    int a;
//    double b;
//};
//    bool great(struct A k1,struct A k)
//    {
//        if (k1.a < k.a)
//            return 1;
//        else if (k1.a > k.a)
//            return 0;
//        return k1.b > k.b;
//    }
//    struct A ans[110];
//int main()
//{
//    
//    int N;
//    cin >> N;
//    for (int i = 0; i < N; i++)
//    {
//        string name;
//        double n;
//        cin >>name>> n;
//        double sum = 0;
//        unordered_map<int, int>mp;
//        for (int i = 0; i < n; i++)
//        {
//            long long x;
//            cin >> x;
//            sum += x;
//            mp[x]++;
//        }
//        ans[i].a = mp.size();
//        ans[i].b =n/mp.size();
//        ans[i].name = name;
//    }
//    for(int i=0;i<N;i++)
//        for (int j = i; j < N; j++)
//        {
//            if (great(ans[i], ans[j]))
//                swap(ans[i], ans[j]);
//        }
//    int i = 0;
//    for (i = 0; i < N && i < 3; i++)
//        cout << ans[i].name << ' ';
//    while (i < 3)
//        cout << '-' << ' ';
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct K {
//    int a, b;
//    bool operator<(K k)
//    {
//        return a < k.a;
//    }
//}test[1010];
//int dp[600010];
//int main()
//{
//    int N, M;
//    cin >> N >> M;
//    int sum = 0;
//    for (int i = 1; i <= N; i++)
//    {
//        cin >> test[i].a;
//        sum += test[i].a;
//    }
//    for (int i = 1; i <= N; i++)
//        cin >> test[i].b;
//    M = min(M, sum);
//    for (int i = 1; i <= N; i++)
//        for (int j = M; j >= test[i].a; j--)
//            dp[j] = max(dp[j], dp[j - test[i].a] + test[i].b);
//    cout << dp[M];
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct A
//{
//    string name;
//    int a;
//    double b;
//    bool operator<(A k)
//    {
//        if (a > k.a)
//            return 1;
//        else if (a < k.a)
//            return 0;
//        return b < k.b;
//    }
//};
//template<class T>
//class les
//{
//    bool operator()(A k1, A k)
//    {
//        if (k1.a < k.a)
//            return 1;
//        else if (k1.a > k.a)
//            return 0;
//        return k1.b > k.b;
//    }
//};
//struct A ans[110];
//int main()
//{
//
//    int N;
//    cin >> N;
//    priority_queue<struct A, vector<struct A>, les<struct A>()>pq;
//    for (int i = 0; i < N; i++)
//    {
//        string name;
//        double n;
//        cin >> name >> n;
//        double sum = 0;
//
//        unordered_map<int, int>mp;
//        for (int i = 0; i < n; i++)
//        {
//            long long x;
//            cin >> x;
//            sum += x;
//            mp[x]++;
//        }
//        ans[i].a = mp.size();
//        ans[i].b = n / mp.size();
//        ans[i].name = name;
//        A aa = pq.top();
//        if (pq.size() < 3)
//            pq.push(ans[i]);
//
//        else if (aa < ans[i])
//        {
//            pq.pop();
//            pq.push(ans[i]);
//        }
//
//    }
//    vector<string>v;
//    while (pq.size())
//    {
//        v.push_back(pq.top().name);
//        pq.pop();
//    }
//    int j = 0;
//    for (int i = v.size() - 1; i >= 0; i--, j++)
//        cout << v[i];
//    {
//        if (j != 2)
//            cout << ' ';
//    }
//    while (j < 3)
//    {
//       
//        cout << '-';
//        if (j != 2)
//            cout << ' ';
//        j++;
//    }
//    cout << endl;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int e[100010], ne[100010], h[100010];
//int idx = 0;
//vector<int>dang(110);
//int cur;
//void add(int a, int b)
//{
//    e[idx] = b;
//    if (h[a] == -1)
//    {
//        h[a] = idx;
//        ne[idx++] = -1;
//    }
//    else
//    {
//        int k;
//        for (k = h[a]; ne[k] != -1; k = ne[k])
//            ;
//        ne[k] = idx;
//        ne[idx++] = -1;
//    }
//}
//int main()
//{
//    int N, M;
//    cin >> N >> M;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < N; i++)
//    {
//        int b;
//        cin >> b;
//        for (int j = 0; j < b; j++)
//        {
//            int x;
//            cin >> x;
//            add(i + 1, x);
//        }
//    }
//    cur = 1;
//    for (int i = 0; i < M; i++)
//    {
//        int a, b;
//        cin >> a;
//        if (a == 0)
//        {
//    
//            cin >> b;
//            int j = h[cur];
//            b--;
//            while (b--)
//                j = ne[j];
//            cur = e[j];
//        }
//        else if (a == 1)
//        {
//         
//            cin >> b;
//                dang[b] = cur;
//                cout << cur << endl;
//        }
//        else
//        {
//           
//            cin >> b;
//            cur = dang[b];
//        }
//    }
//    cout << cur;
//    return 0;
//}
//bool operator<(A k)
//{
//    if (a > k.a)
//        return 1;
//    else if (a < k.a)
//        return 0;
//    return b < k.b;
//}
//#include<bits/stdc++.h>
//using namespace std;
//struct A
//{
//    string name;
//    int a;
//    double b;
//
//};
//struct A ans[110];
//int main()
//{
//
//    int N;
//    cin >> N;
//    for (int i = 0; i < N; i++)
//    {
//        string name;
//        double n;
//        cin >> name >> n;
//        double sum = 0;
//        set<int>mp;
//        for (int i = 0; i < n; i++)
//        {
//            long long x;
//            cin >> x;
//            mp.insert(x);
//        }
//        ans[i].a = mp.size();
//        ans[i].b = n / mp.size();
//        ans[i].name = name;
//    }
//    sort(ans, ans + N, [](auto& A, auto& B) {return A.a == B.a ? (A.b < B.b) : A.a > B.a});
//    int i = 0;
//    for (i = 0; i < N && i < 3; i++)
//    {
//        cout << ans[i].name;
//        if (i != 2)
//            cout << ' ';
//    }
//    while (i < 3)
//    {
//        cout << '-';
//        if (i != 2)
//            cout << ' ';
//    }
//    cout << endl;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int T;
//    cin >> T;
//    while (T--)
//    {
//        int n;
//        cin >> n;
//        int a = 0;
//        vector<int>v;
//        for (int i = 0; i < n; i++)
//        {
//            int x;
//            cin >> x;
//            v.push_back(x);
//        }
//        sort(v.begin(), v.end());
//        vector<int>ans;
//        for (int j = v.size() - 1; j >= 0; j--)
//        {
//            int b = 0;
//            while (j && v[j] == v[j - 1])
//            {
//                b++;
//                j--;
//            }
//            ans.push_back(b + 1);
//        }
//        int i;
//        for (i = 0; i < ans.size(); i++)
//        {
//            if (ans[i] % 2)
//            {
//                cout << "YES" << endl;
//                break;
//            }
//        }
//        if (i == ans.size())
//        cout << "NO" << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int T;
//    cin >> T;
//    while (T--)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        vector<int>v(a + 1, -1);
//        int sum = b - c + 1;
//        int m = c - 1;
//        int n = a - b;
//        n -= sum;
//        m -= sum;
//        for (int i = c; i <= b; i++)
//            v[i] = 1;
//        for (int i = a; n > 0; i--, n--)
//            v[i] = 1;
//        for (int i = 1; m > 0; i++, m--)
//            v[i] = 1;
//        for (int i = 1; i <= a; i++)
//            cout << v[i] << ' ';
//        cout << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//long long a[200010];
//int main()
//{
//    int T;
//    cin >> T;
//    while (T--)
//    {
//        long long n;
//        cin >> n;
//        long long sum = 0;
//
//        for (int i = 0; i < n; i++)
//            cin >> a[i];
//        vector<int>v;
//        for (int kk = 0; kk < 2; kk++)
//        {
//            long long mex = 0;
//            unordered_map<int, int>mp;
//            for (int i = 0; i < n; i++)
//            {
//                sum += a[i];
//                mp[a[i]]++;
//                if (mp[a[i]] > 1)
//                    mex = max(mex, a[i]);
//                a[i] = mex;
//            }
//        }
//        long long i = 0;
//        for (i = 0; i < n; i++)
//            sum += a[i] * (n - i);
//        cout << sum << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//using ll = long long;
//
//void solve() {
//    int n; cin >> n;
//    int a[1000];
//    ll sum = 0;
//    for (int i = 1; i <= n; i++) {
//        cin >> a[i];
//    }
//
//    for (int t = 0; t < 2; t++) {
//        int cnt[1000];
//        memset(cnt, 0, sizeof cnt);
//        int mx = 0;
//        for (int i = 1; i <= n; i++) {
//            sum += a[i];
//            if (cnt[a[i]]) {
//                mx = max(mx, a[i]);
//            }
//            cnt[a[i]] = 1;
//            a[i] = mx;
//        }
//    }
//    for (int i = 1; i <= n; i++) sum += 1LL * (n - i + 1) * a[i];
//    cout << sum << '\n';
//}
//int main()
//{
//    int t; cin >> t;
//    while (t--) {
//        solve();
//    }
//    return 0;
//}
//#include <bits/stdc++.h>
//using namespace std;
//#define m_p make_pair
//#define all(x) (x).begin(),(x).end()
//#define sz(x) ((int)(x).size())
//#define fi first
//#define se second
//typedef long long ll;
//const int N = 200005;
//
//int n;
//int a[N];
//
//bool c[N];
//void doit()
//{
//    for (int i = 1; i <= n; ++i)
//        c[i] = false;
//    int maxu = 0;
//    for (int i = 1; i <= n; ++i)
//    {
//        if (c[a[i]])
//            maxu = max(maxu, a[i]);
//        c[a[i]] = true;
//        a[i] = maxu;
//    }
//}
//
//void solv()
//{
//    cin >> n;
//    for (int i = 1; i <= n; ++i)
//        cin >> a[i];
//
//    ll ans = 0;
//    for (int i = 1; i <= n; ++i)
//        ans += a[i];
//    doit();
//    for (int i = 1; i <= n; ++i)
//        ans += a[i];
//    doit();
//
//    for (int i = 1; i <= n; ++i)
//        ans += (n - i + 1) * 1LL * a[i];
//    cout << ans << "\n";
//}
//
//int main()
//{
//    int tt = 1;
//    cin >> tt;
//    while (tt--)
//    {
//        solv();
//    }
//    return 0;
//}
